package com.sci99.ex.util;

import java.util.List;
import java.util.Stack;

import com.sci99.ex.model.Department;
import com.sci99.ex.model.DptNode;

public class TreeUtil {

	public static DptNode build(List<Department> l) {
		Stack<DptNode> stackContainer = new Stack<>();
		for (int i = 0; i < l.size(); i++) {
			Department d = l.get(i);
			DptNode node = new DptNode(d);
			node.setDep(d.getDep());
			if (d.getRgt() == d.getLft() + 1) {
				if (stackContainer.empty()) {
					return node;
				}
				DptNode pop = stackContainer.pop();
				while (pop.getDep() >= node.getDep()) {
					DptNode temp = stackContainer.pop();
					temp.appendChild(pop);
					stackContainer.push(temp);
					pop = stackContainer.pop();
				}
				pop.appendChild(node);
				stackContainer.push(pop);
			} else {
				if (!stackContainer.empty()) {// 判断是不是同一层的 如果不是的话就压缩栈
					while (d.getDep() <= stackContainer.peek().getDep()) {
						DptNode temp1 = stackContainer.pop();
						DptNode temp2 = stackContainer.pop();
						temp2.appendChild(temp1);
						stackContainer.push(temp2);
					}
				}
				stackContainer.push(node);
			}
		}
		// 压缩为一个节点。
		while (stackContainer.size() > 1) {
			DptNode T1 = stackContainer.pop();
			DptNode T2 = stackContainer.pop();
			T2.appendChild(T1);
			stackContainer.push(T2);
		}
		return stackContainer.pop();
	}

}
